class Solution {
public:
    int left;
    int right;
    int _n;
    string path;
    vector<string> v;
    vector<string> generateParenthesis(int n) {
        _n=n;
        dfs();
        return v;
    }

    void dfs()
    {
        if(right==_n)
        {
            v.push_back(path);
        }

        //(
        if(left<_n)
        {
            path.push_back('(');
            left++;
            dfs();
            path.pop_back();
            left--;
        }
        

        //)
        if(left>right)
        {
            path.push_back(')');
            right++;
            dfs();
            path.pop_back();
            right--;
        }
        
    }
};
